
// 1027.最长等差数列
class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        // 使用动态规划来进行解决
        // 用一个unordered_map<int,int>,其中first表示公差, second表示长度
        int n = nums.size();
        vector<unordered_map<int,int>>  dp(n);

        int ret = 0;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0 ; j < i ; j++)
            {
                int diff = nums[i] - nums[j];
                if(dp[j].count(diff)) dp[i][diff] = dp[j][diff] + 1;
                else dp[i][diff] = 2;

                ret = max(ret , dp[i][diff]);
            }
        }
        return ret;
    }
};